package com.example.arithmeticleetcode.learnArithmetic2.sort;

import com.example.arithmeticleetcode.learnArithmetic2.sort.utils.Asserts;
import com.example.arithmeticleetcode.learnArithmetic2.sort.utils.Integers;

import java.util.Arrays;

/**
 * @program: arithmetic-leetcode
 * @description: 比较排序
 * @author: FangZhen
 * @create: 2020-11-04 15:05
 **/
public class Main {

    public static void main(String[] args) {
//        Integer[] arr = Integers.random(20, 1, 100);
//        Integer[] arr = Integers.ascOrder(1, 10000);
//        Integer[] arr = Integers.tailAscOrder(1, 20, 5);

//        Integer[] arr2 = Integers.copy(arr);
//        Integer[] arr3 = Integers.copy(arr);
//
//
//
//        Times.test("冒泡排序优化前", () -> {
//            BubbleSortV1(arr3);
//        });
//
//
//        Times.test("冒泡排序优化后", () -> {
//            BubbleSortV2(arr2);
//        });
//
//        Times.test("冒泡排序优化记录最后一次指针后", () -> {
//            BubbleSortV3(arr3);
//        });
//
//        Integers.println(arr);
//        Integers.println(arr2);
//        Integers.println(arr3);

//        Times.test("自定义排序", () -> {
//            selectionSort(arr);
//        });

//        Integers.println(arr);
//        Times.test("老师排序", () -> {
//            selectionSort(arr2);
//        });
//        Integers.println(arr2);

        Integer[] arr = Integers.random(10000, 1, 30000);
        testSorts(arr,
                new HeapSort(),
                new BubbleSort3(),
                new SelectionSort(),
                new InsertionSort3(),
                new InsertionSort2(),
                new InsertionSort(),
                new MergeSort(),
                new QuickSort(),
                new ShellSort(),
                new CountingSort(),
                new RedixSort()
        );

//        [6, 126, 10318, 1796, 8365, 14519]

//        int[] array = {2, 4, 8, 8, 8, 12, 14};
//        Asserts.test(BinarySearch.searh(array, 5) == 2);
//        Asserts.test(BinarySearch.searh(array, 1) == 0);
//        Asserts.test(BinarySearch.searh(array, 8) == 5);
//        Asserts.test(BinarySearch.searh(array, 15) == 7);


    }

    static void testSorts(Integer[] array, Sort... sorts) {
        for (Sort sort : sorts) {
            Integer[] newArrays = Integers.copy(array);
            sort.sort(newArrays);
            Asserts.test(Integers.isAscOrder(newArrays));
        }

        Arrays.sort(sorts);

        for (Sort sort : sorts) {
            System.out.println(sort);
        }
    }

    /**
     * 老师 选择排序优化
     *
     * @param arr
     */
    private static void selectionSortV2(Integer[] arr) {
        for (int end = arr.length - 1; end > 0; end--) {
            int maxIndex = 0;
            for (int begin = 0; begin <= end; begin++) {
                if (arr[maxIndex] < arr[begin]) {
                    maxIndex = begin;
                }
            }
            int temp = arr[maxIndex];
            arr[maxIndex] = arr[end];
            arr[end] = temp;
        }
    }

    /**
     * 老师 选择排序
     *
     * @param arr
     */
    private static void selectionSortV1(Integer[] arr) {
        for (int end = arr.length - 1; end > 0; end--) {
            int maxIndex = 0;
            for (int begin = 0; begin <= end; begin++) {
                if (arr[maxIndex] < arr[begin]) {
                    maxIndex = begin;
                }
            }
            int temp = arr[maxIndex];
            arr[maxIndex] = arr[end];
            arr[end] = temp;
        }
    }

    /**
     * 自定义 选择排序
     *
     * @param arr
     */
    private static void selectionSort(Integer[] arr) {
        for (int end = arr.length - 1; end > 0; end--) {
            int max = Integer.MIN_VALUE;
            int index = -1;
            for (int begin = 0; begin <= end; begin++) {
                if (max < arr[begin]) {
                    max = arr[begin];
                    index = begin;
                }
            }
            arr[index] = arr[end];
            arr[end] = max;
        }
    }

    /**
     * 老师的冒泡排序 对局部有排序，记录最后一次指针
     *
     * @param arr
     */
    private static void BubbleSortV3(Integer[] arr) {
        for (int end = arr.length - 1; end > 0; end--) {
            //记录最后一次交换的位置 初始值为完全有序的时候准备的
            int sortedIndex = 1;
            for (int begin = 1; begin <= end; begin++) {
                if (arr[begin] > arr[begin - 1]) {
                    sortedIndex = begin;
                    int temp = arr[begin];
                    arr[begin] = arr[begin - 1];
                    arr[begin - 1] = temp;
                }
            }
            end = sortedIndex;
        }
    }

    /**
     * 老师的冒泡排序 优化后
     *
     * @param arr
     */
    private static void BubbleSortV2(Integer[] arr) {
        for (int end = arr.length - 1; end > 0; end--) {
            //使用flag进行标记结束
            boolean flag = true;
            for (int begin = 1; begin <= end; begin++) {
                if (arr[begin] > arr[begin - 1]) {
                    flag = false;
                    int temp = arr[begin];
                    arr[begin] = arr[begin - 1];
                    arr[begin - 1] = temp;
                }
            }
            if (flag) {
                break;
            }
        }
    }

    /**
     * 老师的冒泡排序未优化
     *
     * @param arr
     */
    private static void BubbleSortV1(Integer[] arr) {
        for (int end = arr.length - 1; end > 0; end--) {
            //使用flag进行标记结束
//            boolean flag = true;
            for (int begin = 1; begin <= end; begin++) {
                if (arr[begin] > arr[begin - 1]) {
//                    flag = false;
                    int temp = arr[begin];
                    arr[begin] = arr[begin - 1];
                    arr[begin - 1] = temp;
                }
            }
//            if (flag) {
//                break;
//            }
        }
    }

    /**
     * 自定义的冒泡排序
     */
    private static void bubbleSort(int[] arr) {
        for (int i = 0, len = arr.length; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                if (arr[i] < arr[j]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }


}
